/*
 * C/C++ KLIB Project
 * 
 * Copyright (c) 2012 Ken Zhang (cpp.china@gmail.com)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA  02111-1307  USA
 *
 */

#include "klib.h"
#include <stdlib.h>
#include <string.h>

list_node_t *list_node_create(void *data)
{
	list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
	if (node != NULL) {
		node->data = data;
		node->prev = NULL;
		node->next = NULL;
	}
	return node;
}

void list_node_destroy(list_node_t *node)
{
	if (node != NULL) {
		list_node_delete(node);
		memset(node, 0, sizeof(list_node_t));
		free(node);
	}
}

void list_insert_before(list_node_t *pos, list_node_t *node)
{
	if (pos->prev) {
		pos->prev->next = node;
		node->prev = pos->prev;
		pos->prev = node;
		node->next = pos;
	}
	else {
		node->next = pos;
		pos->prev = node;
	}
}

void list_insert_after(list_node_t *pos, list_node_t *node)
{
	if (pos->next) {
		pos->next->prev = node;
		node->next = pos->next;
		pos->next = node;
		node->prev = pos;
	}
	else {
		pos->next = node;
		node->prev = pos;
	}
}

list_node_t *list_node_delete(list_node_t *node)
{
	if (node != NULL) {
		if (node->prev) {
			node->prev->next = node->next;
		}
		if (node->next) {
			node->next->prev = node->prev;
		}
	}
	return node;
}

int list_index_of(const list_node_t *node)
{
	int index = 0;
	if (node == NULL)
		return -1;

	while (node->prev) {
		++index;
		node = node->prev;
	}
	return index;
}

int list_count(const list_node_t *any)
{
	int n = 0;
	const list_node_t *node;

	if (any == NULL)
		return 0;

	node = any;
	while (node) {
		++n;
		node = node->next;
	}

	node = any->prev;
	while (node) {
		++n;
		node = node->prev;
	}

	return n;
}

void _list_swap_data(void *base, int i, int j)
{
	void ***idx = (void ***)base;
	register void **tmp = idx[i];
	idx[i] = ((void **)base)[j];
	((void **)base)[j] = tmp;
}

void list_sort(const list_node_t *begin, int count, int (*compare)(const void *, const void*))
{
	int n = list_count(begin);
	void **idx;

	if (n > 0) {
		if (count > 0 && count < n) {
			n = count;
		}
		idx = malloc(sizeof(void *) * n);
		n = 0;
		while (begin) {
			idx[n++] = &(begin->data);
			begin = begin->next;
		}
		quicksort(idx, get_element_ptr, 0, n - 1, compare, swap_ptr);
		free(idx);
	}
}

list_node_t *list_node_at(list_node_t *begin, int index)
{
	list_node_t *node = begin;
	if (index > 0) {
		while (index-- > 0) {
			if (node == NULL)
				return NULL;
			else
				node = node->next;
		}
	}
	else {
		while (index++ < 0) {
			if (node == NULL)
				return NULL;
			else
				node = node->prev;
		}
	}
	return node;
}

list_node_t *list_head_of(list_node_t *any)
{
	list_node_t *node = any;
	while (node && node->prev) {
		node = node->prev;
	}
	return node;
}

list_node_t *list_tail_of(list_node_t *any)
{
	list_node_t *node = any;
	while (node && node->next) {
		node = node->next;
	}
	return node;
}

void list_push_back(list_node_t *any, list_node_t *node)
{
	if (any != NULL) {
		list_node_t *end = list_tail_of(any);
		list_insert_after(end, node);
	}
}

void list_push_front(list_node_t *any, list_node_t *node)
{
	if (any) {
		list_node_t *begin = list_head_of(any);
		list_insert_before(begin, node);
	}
}

int list_foreach(list_node_t *begin, void (*fn_proc_node)(list_node_t *))
{
	int n = 0;
	list_node_t *node = begin, *next;

	while (node) {
		next = node->next;
		fn_proc_node(node);
		node = next;
		++n;
	}
	return n;
}

int list_foreach_data(list_node_t *begin, void (*fn_proc_data)(void *))
{
	int n = 0;
	list_node_t *node = begin, *next;

	while (node) {
		next = node->next;
		fn_proc_data(node->data);
		node = next;
		++n;
	}
	return n;
}

#include "var.h"

void test_output_data(void *data)
{
	printf("%s\n", tostring(((var_t *)data)));
}

void test_list_sort()
{
	list_node_t *list = list_node_create(NULL);
	int i;

	srand(time(NULL));
	for (i = 0; i < 10; i++) {
		list_push_back(list, list_node_create(var_create(var_int((void *)(rand() % 100)))));
	}
	list_foreach_data(list->next, test_output_data);
	list_sort(list->next, -1, var_compare);
	puts("");
	list_foreach_data(list->next, test_output_data);
}
